package edu.whu.rose.clock.kps.algorithm.blinks.index;

import java.util.HashMap;
import java.util.NoSuchElementException;

import edu.whu.rose.clock.ssql.util.SubgraphMatrix;
import edu.whu.rose.clock.util.priorityqueue.FibonacciHeapPQ;
import edu.whu.rose.clock.util.priorityqueue.UnderflowException;

public class GroupIteratorInBlock {

	private final SubgraphMatrix subgraph;
	private final int[] initVertexes;
	
	private HashMap<Integer, GroupSPVertex> set;
	private FibonacciHeapPQ<GroupSPVertex> queue;

	public GroupIteratorInBlock(SubgraphMatrix subgraph, int[] initVertexes) {
		this.subgraph = subgraph;
		this.initVertexes = initVertexes;
		
		this.set = new HashMap<Integer, GroupSPVertex>();
		this.queue = new FibonacciHeapPQ<GroupSPVertex>();
		
		int pos = 0;
		for (int i = 0; i < subgraph.getN(); i++) {
			GroupSPVertex spv = null;
			if (pos < initVertexes.length && subgraph.getVertex(i) == initVertexes[pos]) {
				spv = new GroupSPVertex(subgraph.getVertex(i), 0.0D, initVertexes[pos]);
				spv.setPredecessor(-1);
				pos++;
			}
			else {
				spv = new GroupSPVertex(subgraph.getVertex(i), Double.MAX_VALUE, 0);
			}
			int indexID = queue.enqueue(spv);
			spv.setIndexID(indexID);
			set.put(new Integer(subgraph.getVertex(i)), spv);
		}
	}
	
	public boolean hasNext() {
		try {
			return ! (peek() == Double.MAX_VALUE);
		}
		catch (UnderflowException ex) {
			return false;
		}
	}
	
	public GroupSPVertex next() {
		if (queue.isEmpty()) {
			throw new NoSuchElementException();
		}
		GroupSPVertex min = null;
		try {
			min = queue.dequeueMin();
		}
		catch (UnderflowException ex) {
			ex.printStackTrace();
		}
		if (!set.containsKey(min.getID())) {
			System.out.println("Error: found exsiting shortest path");
		}
		set.remove(min.getID());
		int[] neighbors = subgraph.genNeighbors(min.getID());
		for (int i = 0; i < neighbors.length; i++) {
			if (!set.containsKey(neighbors[i])) {
				continue;
			}
			GroupSPVertex spv = set.get(neighbors[i]);
			double dis = min.getDistance() + 1.0D;
			if (dis < spv.getDistance()) {
				spv.setDistance(dis);
				spv.setPredecessor(min.getID());
				spv.setSource(min.getSource());
				relax(spv);
			}
		}
		return min;
	}
	
	private void relax(GroupSPVertex spv) {
		try {
			queue.decreaseKey(spv.getIndexID(), spv);
		}
		catch (UnderflowException ex) {
			ex.printStackTrace();
		}
	}

//	public double getDistance(int id) {
//		return set[id - 1].getDistance();
//	}

	public double peek() throws UnderflowException {
		return queue.findMin().getDistance();
	}

//	public int compareTo(GroupIteratorInSubgraph x) {
//		try {
//			if (peek() < x.peek()) {
//				return -1;
//			}
//			else if (peek() == x.peek()) {
//				return 0;
//			}
//			else {
//				return 1;
//			}
//		}
//		catch (UnderflowException ex) {
//			ex.printStackTrace();
//			System.exit(1);
//			return 0;
//		}
//	}

}
